package com.huang.leetcode.stack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * @Author：CreateSequence
 * @Date：2020-07-30 21:26
 * @Description：合并区间
 */
public class PB56 {

    public int[][] merge(int[][] intervals) {

        /**
         * 1.先对区间进行排序，左区间小的排前面，
         * 2.假设有a区间和b区间，其有三种状态：包含，部分包含，分离：
         * 2.1当a[1]>=b[0]是说明存在包含部分，取a[1]和b[1]中最大者与a[0]组成新区间
         * 2.2否则说明两区间分离，直接装入新数组
         */

        //排序
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        Stack<int[]> stack = new Stack<>();

        for (int[] area : intervals) {
            if (stack.isEmpty()) {
                stack.push(area);
            }else {
                int[] preArea = stack.pop();
                //判断区间状态
                if (preArea[1] >= area[0]) {
                    int[] newArea = {preArea[0], Math.max(preArea[1], area[1])};
                    stack.push(newArea);
                }else {
                    stack.push(preArea);
                    stack.push(area);
                }
            }
        }

        int[][] res = new int[stack.size()][2];
        stack.toArray(res);

        return res;
    }

}
